package com.topcoder.tcow10;

public class SequencePermutation {
	public int determineConfigurations(int N, int M) {
		int MOD = 1000000009;
		int[][] dp = new int[N+1][M+1];
		int[] sum = new int[M+2];
		
		for (int i=0; i<=M; i+=2) {
			dp[0][i] = 1;
		}
		
		for (int i=1; i<=N; i++) {
			sum[0] = 0;
			for (int j=0; j<=M; j++) {
				sum[j+1] = (sum[j] + dp[i-1][j]) % MOD;
			}
			
			for (int j=0; j<=M; j++) {
				int lo = Math.max(0, j-i+1);
				dp[i][j] = (sum[j+1] - sum[lo] + MOD) % MOD;
			}
		}
		
		return dp[N][M];
	}
}
